BOJ

[Silver IV] 근수 - 31882

문제 링크

성능 요약

메모리: 186884 KB, 시간: 588 ms

분류

수학, 문자열

제출 일자

2025년 9월 2일 00:59:18

문제 설명

요즘 K512에서는 '근수 게임'이라는 놀이가 엄청난 인기를 끌고 있다. 근수 게임은 주어진 문자열에 대하여 근수 점수를 빨리 계산하여 먼저 외치는 게임이다. 근수 점수는 주어진 문자열에 있는 모든 연속된 부분 문자열에 대해 다음과 같이 점수를 더한 것으로 계산된다.

1. 부분 문자열 $2$는 '근수'로 간주하여 등장할 때마다 $1$점을 더한다.
2. 부분 문자열 $22$는 '근근수'로 간주하여 등장할 때마다 $2$점을 더한다.
3. 연속된 $k$ $(k\ge 3)$개의 $2$로 이루어진 부분 문자열 $22\dots 2$는 '근근...근수'로 간주하여 등장할 때마다 $k$점을 더한다.
4. 그 외 부분 문자열은 $0$점을 더한다.

이때 '근근...근수'끼리는 서로 겹칠 수 있다는 점에 유의해야 한다. 예를 들어 $112223223$이라는 문자열은 '근수' $5$개, '근근수' $3$개, '근근근수' $1$개가 등장해 $(1\times 5)+(2\times 3)+(3\times 1)=14$점의 근수 점수를 가진다.

근수는 자신의 이름을 딴 근수 게임의 최강자 자리를 차지하기 위해 문자열을 입력했을 때, 그 문자열의 근수 점수를 빠르게 구해주는 프로그램을 작성하려고 한다. 근수를 도와 프로그램을 작성해 보자.

입력

첫 번째 줄에 문자열의 길이 $N(1\le N\le {10}^6)$가 주어진다.

두 번째 줄에는 길이 $N$의 문자열 $S$가 주어진다. 문자열은 모두 숫자로 이루어져 있으며, $0$으로 시작할 수 있다.

출력

문자열 $S$의 근수 점수를 출력하여라.

소스 코드

• 근수.java